package _back_tracking

import org.junit.Assert
import org.junit.Test

/*
https://leetcode.cn/problems/palindrome-partitioning/description/
https://programmercarl.com/0131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2.html

131. 分割回文串
给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：

输入：s = "a"
输出：[["a"]]
 */
class leetcode_131 {
    @Test
    fun test_1() {
        val actual = partition("aab")
        val expect = arrayListOf(arrayListOf("a", "a", "b"), arrayListOf("aa", "b"))
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_2() {
        val actual = partition("a")
        val expect = arrayListOf(arrayListOf("a"))
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    @Test
    fun test_3() {
        val actual = partition("cbbbcc")
        val expect = arrayListOf(
            arrayListOf("c", "b", "b", "b", "c", "c"),
            arrayListOf("c", "b", "b", "b", "cc"),
            arrayListOf("c", "b", "bb", "c", "c"),
            arrayListOf("c", "b", "bb", "cc"),
            arrayListOf("c", "bb", "b", "c", "c"),
            arrayListOf("c", "bb", "b", "cc"),
            arrayListOf("c", "bbb", "c", "c"),
            arrayListOf("c", "bbb", "cc"),
            arrayListOf("cbbbc", "c"),
        )
        Assert.assertEquals(expect.toString(), actual.toString())
    }

    fun partition(s: String): List<List<String>> {
        /*
        回溯法
        注意：
        1 切割后的所有字串都是回文串
        2 在叶子节点收集数据
         */
        val path: ArrayList<String> = ArrayList<String>()
        val result: ArrayList<ArrayList<String>> = ArrayList<ArrayList<String>>()
        backtrcking(s, 0, path, result)
        return result
    }

    private fun backtrcking(s: String, startIndex: Int, path: ArrayList<String>, result: ArrayList<ArrayList<String>>) {
        // 1 确定函数参数以及返回值
        // 2 确定终止条件
        // 终止条件
        if (startIndex == s.length) { // 切割位置已经移动到了字符串后面
            // 收集结果
            val items: ArrayList<String> = ArrayList<String>()
            items.addAll(path)
            result.add(items)
            return
        }

        for (i in startIndex..s.length - 1) { // [startIndex, size)
            // i  - 宽度
            // startIndex-深度
            // 处理
            val subStr: String = s.substring(startIndex..i) // TODO: [startIndex, i]
//            println("[$startIndex, $i] = $subStr")
            // TODO:string.reversed()
            if (subStr != subStr.reversed()) { // 判断不是回文，继续遍历
                continue
            }
            path.add(subStr)
//            println("path=${path.toString()}")

            // 递归
            backtrcking(s, i + 1, path, result)

            // 回溯
            // TODO：删除最后一个元素，不是删除path.remove(t),否则得到的结果和预期不同
            path.removeAt(path.size - 1)
        }
    }
}